﻿using System;
using System.Collections.Generic;
using System.Text;

namespace AlgorithmTest
{
    // T_[四个数字排序]_[算法名]
    public class T_0043_MergeTrees : IAlgorithm
    {
        // 617. 合并二叉树

        // 给定两个二叉树，想象当你将它们中的一个覆盖到另一个上时，两个二叉树的一些节点便会重叠。
        // 你需要将他们合并为一个新的二叉树。合并的规则是如果两个节点重叠，那么将他们的值相加作为节点合并后的新值，
        // 否则不为 NULL 的节点将直接作为新二叉树的节点。

        // 注意: 合并必须从两个树的根节点开始。
        // 注意：该题题目中说的是新二叉树，所以不能对原树进行修改。

        public void Test()
        {
            // 算法参数定义
            var root1 = new TreeNode(1)
            {
                left = new TreeNode(3)
                {
                    left = new TreeNode(5)
                },
                right = new TreeNode(2)
            };
            var root2 = new TreeNode(2)
            {
                left = new TreeNode(1)
                {
                    right = new TreeNode(4)
                },
                right = new TreeNode(3)
                {
                    right = new TreeNode(7)
                }
            };
            // 算法执行与打印
            var newTree = MergeTrees(root1, root2);
            Console.WriteLine(newTree);
        }

        // 算法
        // DFS
        public TreeNode MergeTrees(TreeNode root1, TreeNode root2)
        {
            if (root1 == null)
                return root2;
            if (root2 == null)
                return root1;
            var merged = new TreeNode(root1.val + root2.val)
            {
                left = MergeTrees(root1.left, root2.left),
                right = MergeTrees(root1.right, root2.right)
            };
            return merged;
        }
    }
}
